#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "tree.h"

#define RB_RED 0
#define RB_BLACK 1
#define GRANDPRENT(x) (!x->parent?NULL:x->parent->parent)
#define BROTHER(x) (!x->parent?NULL:(x==x->parent->left?x->parent->right:x->parent->left))
#define UNCLE(x) (!x->parent?NULL:BROTHER(x->parent))
#define L_NEPHEW(x) (!BROTHER(x)?NULL:BROTHER(x)->left)
#define R_NEPHEW(x) (!BROTHER(x)?NULL:BROTHER(x)->right)
#define EXCH_COLOR(p, q) do{			\
				assert((p) && (q)); 	\
				int bf = (p)->bf;	\
				(p)->bf = (q)->bf;	\
				(q)->bf = bf;	\
				}while(0)

static node *_alloc_node(int data)
{
	node *p = (node *)malloc(sizeof(struct node));
	if(!p){
		fprintf(stderr,"malloc failed !!!\n");
		exit(9);
	}
	p->left = p->right = p->parent = NULL;
	p->bf = RB_RED;
	p->data = data;
	return p;
}

node *rb_search(node *root, int data)
{
	if(!root){
		return NULL;
	}
	node *p = root;
	while(p){
		if(p->data > data){
			p = p->left;
		}else if(p->data < data){
			p = p->right;
		}else{
			return p;
		}
	}
	return NULL;
}

static node *l_rotate(node **rootp, node *p)
{
	assert(rootp && *rootp && p && p->right);
	node *q = p->right;
	p->right = q->left;
	q->left = p;
	if(!p->parent){
		*rootp = q;
	}else if(p->parent->left == p){
		p->parent->left = q;
	}else{
		p->parent->right = q;
	}
	q->parent = p->parent;
	p->parent = q;
	return q;
}
static node *r_rotate(node **rootp, node *p)
{
	assert(rootp &&  *rootp && p && p->left);
	node *q = p->left;
	p->left = q->right;
	q->right = p;
	if(!p->parent){
		*rootp = q;
	}else if(p == p->parent->left){
		p->parent->left = q;
	}else{
		p->parent->right = q;
	}
	q->parent = p->parent;
	p->parent = q;
	return q;
}

static node *l_balence(node **rootp, node *p)
{
	assert(rootp && *rootp && p && p->parent && p->parent->parent && p->parent==p->parent->parent->right);
	if(p == p->parent->left){
		r_rotate(rootp, p->parent);
	}
	EXCH_COLOR(p->parent, p->parent->parent);
	return l_rotate(rootp, p->parent->parent);
}
static node *r_balence(node **rootp, node *p)
{
	assert(rootp && *rootp && p && p->parent && p->parent->parent && p->parent==p->parent->parent->left);
	if(p == p->parent->right){
		l_rotate(rootp, p->parent);
	}
	EXCH_COLOR(p->parent, p->parent->parent);
	return r_rotate(rootp, p->parent->parent);
}

static int insert_fixup(node **rootp, node *p)
{
	assert(rootp && *rootp && p);
//	node *q = NULL;
	while(p->parent && p->parent->bf==RB_RED){
		if(UNCLE(p) && UNCLE(p)->bf==RB_RED){
			p->parent->bf = RB_BLACK;
			UNCLE(p)->bf = RB_BLACK;
			if(p->parent->parent != *rootp){
				p->parent->parent->bf = RB_RED;
			}
			p = p->parent;
		}else{
			if(p->parent==p->parent->parent->left){
				r_balence(rootp, p);
			}else{
				l_balence(rootp, p);
			}
		}
	}
	return 0;
}

node *rb_insert(node **rootp, int data)
{
	assert(rootp);

	if(!*rootp){
		*rootp = _alloc_node(data);
		(*rootp)->bf = RB_BLACK;
		return *rootp;
	}
	
	node *p = *rootp;
	node *q = NULL;
	while(p){
		q = p;
		if(p->data > data){
			p = p->left;
		}else if(p->data < data){
			p = p->right;
		}else{
			return p;
		}
	}
	p = _alloc_node(data);
	p->parent = q;
	if(q->data > data){
		q->left = p;
	}else{
		q->right = p;
	}
	insert_fixup(rootp, p);
	return p;
}

static int delete_fixup(node **rootp, node *p)
{
	assert(rootp && *rootp && p);
	while(p->parent->bf == RB_BLACK){
		if(BROTHER(p) && BROTHER(p)->bf == RB_RED){
			EXCH_COLOR(p->parent, BROTHER(p));
			if( p == p->parent->left){
				l_rotate(rootp, p->parent);
			}else{
				r_rotate(rootp, p->parent);
			}
		}
		if(BROTHER(p) && BROTHER(p)->bf==RB_BLACK && L_NEPHEW(p) && R_NEPHEW(p) &&
			L_NEPHEW(p)->bf==RB_BLACK && R_NEPHEW(p)->bf==RB_BLACK){
			BROTHER(p)->bf = RB_RED;
			p = p->parent;
			continue;
		}
		if(BROTHER(p) && BROTHER(p)->bf==RB_BLACK && L_NEPHEW(p) && R_NEPHEW(p) &&
			 L_NEPHEW(p)->bf==RB_RED && R_NEPHEW(p)->bf==RB_BLACK){
			
		}
		if(BROTHER(p) && BROTHER(p)->bf==RB_BLACK && L_NEPHEW(p) && R_NEPHEW(p) &&
			 R_NEPHEW(p)->bf==RB_RED){
		}
	}
	return 0;
}

node *rb_delete(node **rootp, int data)
{
	node *p = rb_search(*rootp, data);
	if(!p){
		return NULL;
	}
	node *q = NULL;
	if(p->left && p->right){
		q = successor(p);
		if(q->right){
			q->right->parent = q->parent;
		}
		p->data = q->data;
		if(q == q->parent->left){
			q->parent->left = q->right;
		}else{
			q->parent->right = q->right;
		}
		delete_fixup(rootp, q);
		q->parent = NULL;
		return q;
	}

	if(p->right){
		q = p->right;
	}else{
		q = p->left;
	}
	if(q){
		q->parent = p->parent;
	}
	if(!p->parent){
		*rootp = q;
	}else if(p == p->parent->left){
		p->parent->left = q;
	}else{
		p->parent->right = q;
	}
	delete_fixup(rootp, p);
	p->parent = NULL;
	return p;
}
